class Solution:
    _MOD = 10 ** 9 + 7

    def numMusicPlaylists(self, n: int, l: int, k: int) -> int:
        # 定义状态矩阵：dp[already][i][j] = 在已听完l首歌时，已听过的歌曲为i首时的选择数量
        dp1 = [0] * (n + 1)
        dp1[0] = 1

        for _ in range(l):
            dp2 = [0] * (n + 1)
            for i in range(n + 1):
                if i > k:
                    dp2[i] = (dp2[i] + dp1[i] * (i - k)) % self._MOD  # 播放已听过的歌
                if i < n:
                    dp2[i + 1] = (dp2[i + 1] + dp1[i] * (n - i)) % self._MOD  # 播放未听过的歌
            dp1 = dp2

        return dp1[n]


if __name__ == "__main__":
    print(Solution().numMusicPlaylists(3, 3, 1))  # 6
    print(Solution().numMusicPlaylists(2, 3, 0))  # 6
    print(Solution().numMusicPlaylists(2, 3, 1))  # 2
